class Solution {
    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return nums;
        }
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }
    private void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int idx = partition(nums, left, right);
        quickSort(nums, left, idx);
        quickSort(nums, ++idx, right);
    }
    private int partition(int[] nums, int left, int right) {
        int idx = left + (int)(Math.random() * (right - left + 1));
        int idxValue = nums[idx];
        // 这个等号还是有必要的呀，不然个数为奇数时容易漏掉中间的数
        while (left <= right) {
            while (nums[left] < idxValue) left++;
            while (nums[right] > idxValue) right--;
            // 上边那个有等号，这个地方也得加上，不然可能死循环，交换意义不大，重点是让left和right往下走一步跳出循环
            if (left <= right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
                right--;
            }
        }
        return right;
    }
}
